1522. Diameter of N-Ary Tree
Medium

Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.

The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

(Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)

 

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

Example 2:

Input: root = [1,null,2,null,3,4,null,5,null,6]
Output: 4

Example 3:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 7

 

Constraints:

  • The depth of the n-ary tree is less than or equal to 1000.
  • The total number of nodes is between [1, 104].
Accepted
9.6K
Submissions
13.8K
Seen this question in a real interview before?
Companies
Similar Questions
Show Hint 1
For the node i, calculate the height of each of its children and keep the first and second maximum heights (max1_i , max2_i).
Show Hint 2
Check all nodes and return max( 2 + max1_i + max2_i ).

Average Rating: 5.00 (6 votes)

Premium

Solution


Overview

We are asked to calculate the diameter of a N-ary tree, which is defined as the longest path between any two nodes in the tree.

At first glance, it seems that we might have to enumerate all pairs of nodes, in order to find out the longest path.

Yet, there are certain insights that would allow us to dramatically reduce the scope of enumeration.

The first insight is that the longest path in a tree can only happen between two leaves nodes or between a leaf node and the root node.

example of paths

The second insight is that each non-leaf node acts as a bridge for the paths between its descendant leaves nodes. If we pick two longest sub-paths from a non-leaf node to its descendant leaves nodes, and combine them together, then the resulting path would be the longest path among all possible ones that are bridged by this non-leaf node.

example of subpaths

As one could see from the above graph, the longest path of the tree would be one of the combined paths from the top two longest sub-paths bridged by a non-leaf node (node 2 in the above graph).

With the above insights, to find the diameter of the tree, it suffices to enumerate all non-leaf nodes and select the top two longest sub-paths bridged by each non-leaf node.

The above idea could be implemented with the help of two important concepts in the tree data structure, namely the height and depth of a node.

In this article, we will present two algorithms with regards to the concept of height and depth respectively.


Approach 1: Distance with Height

Intuition

The height of a node is defined as the length of the longest downward path to a leaf node from that node.

Based on the above definition, a leaf node will have a height of zero.

As we explained in the overview section, the longest path that is bridged by a non-leaf node will come from the combination of two longest sub-paths downward to the leaves nodes from this non-leaf node.

As one might see now, the sub-paths that we mentioned above consist of the top two largest heights of the children nodes.

If we define the top two largest heights of the children nodes as height(node.child_m) and height(node.child_n), then the longest path bridged by this node would be height(node.child_m) + height(node.child_n) + 2.

formula height

Algorithm

Let us first define a function called height(node) which returns the height of the node. The function can be implemented via recursion, based on the following formula:

height(node)=max(height(child))+1, childnode.children \text{height(node)} = \max\big(\text{height(child)}\big) + 1, \space \forall \text{child} \in \text{node.children}

More importantly, within the function of height(node), we need to select the top two largest heights of its children nodes. With these top two largest heights, we calculate the length of the combined path, which would be the candidate as the diameter of the entire tree.

There are two ways to select the top two largest heights:

  • A straight-forward way would be that we keep the heights of all children nodes in an array, and then we sort the array and select the top two largest elements.

  • A constant-space solution would be that we use only two variables which keep track of the current top two largest elements respectively. While we iterate through all the heights, we update the two variables accordingly.

In the following implementation, we opt for the second approach.

Complexity Analysis

Let NN be the number of nodes in the tree.

  • Time Complexity: O(N)\mathcal{O}(N)

    • We enumerate each node in the tree once and only once via recursion.
  • Space Complexity: O(N)\mathcal{O}(N)

    • We employed only constant-sized variables in the algorithm.

    • On the other hand, we used recursion which will incur additional memory consumption in the function call stack. In the worst case where all the nodes are chained up in a single path, the recursion will pile up NN times.

    • As a result, the overall space complexity of the algorithm is O(N)\mathcal{O}(N).


Approach 2: Distance with Depth

Intuition

The depth of a node is the length of the path to the root node.

Still, we would like to know the longest path between two leaves nodes bridged by a non-leaf node. But this time we could calculate it with the concept of depth, rather than height.

If we know the top two largest depths among two leaves nodes starting from the node, namely depth(node.leaf_m) and depth(node.leaf_n), then this longest path could be calculated as the sum of top two largest depths minus the depth of the parent node, namely
depth(node.leaf_m) + depth(node.leaf_n) - 2 * depth(node).

formula depth

Algorithm

Let us define a function called maxDepth(node) which returns the maximum depth of the leaves nodes starting from the node.

Again, we could implement it with recursion, with the following formula:

maxDepth(node)=max(maxDepth(node.child)), childnode.children \text{maxDepth(node)} = \max\big(\text{maxDepth(node.child)}\big), \space \forall \text{child} \in \text{node.children}

Similarly, within the function, we will also select the top two largest depths. With these top two largest depths, we will update the diameter accordingly.

Complexity Analysis

Let NN be the number of nodes in the tree.

  • Time Complexity: O(N)\mathcal{O}(N)

    • We enumerate each node in the tree once and only once via recursion.
  • Space Complexity: O(N)\mathcal{O}(N)

    • We employed only constant-sized variables in the algorithm.

    • On the other hand, we used recursion which will incur additional memory consumption in the function call stack. In the worst case where all the nodes are chained up in a single path, the recursion will pile up NN times.

    • As a result, the overall space complexity of the algorithm is O(N)\mathcal{O}(N).


Report Article Issue

Comments: 5
waynelaizye's avatar
Read More

Simple Python solution:
For every dfs, go through all children's max depth and return max depth of this node. Also calculate the diameter that passes this node.

    def diameter(self, root):
        """
        :type root: 'Node'
        :rtype: int
        """
        self.maxdiameter = 0
        
        def dfs(root):
            depths = [0, 0] # to deal with empty children
            for child in root.children:
                depths.append(dfs(child))
            self.maxdiameter = max(self.maxdiameter, sum(sorted(depths)[-2:])) # sum of top 2 depth
            return max(depths)+1

        dfs(root)
        return self.maxdiameter 

7
Show 2 replies
Reply
Share
Report
tiagsters's avatar
Read More

Beats 99% python solution

class Solution:
    def diameter(self, root: 'Node') -> int:
        """
        :type root: 'Node'
        :rtype: int
        """
        best = 0
        def dfs(root):
            nonlocal best
            max1 = 0
            max2 = 0
            for child in root.children:
                depth = dfs(child)
                depth += 1
                if depth > max1:
                    max1, max2 = depth, max1
                elif depth > max2:
                    max2 = depth
            best = max(best, max1 + max2)
            return max1
        dfs(root)
        return best

1
Reply
Share
Report
shashankg23's avatar
Read More

My C++ solution

class Solution {
	public:
	int dfsoOrPost(Node* root, int& d) {
		if(!root)  return 0;
		
		// distance b/w 2 leaf nodes
		int p1 = 0; // max sbtree path
		int p2 = 0;  // second max  tree path
		for(int i =0 ; i < root->children.size(); i++) {
			int path = dfsoOrPost(root->children[i], d);   
			// max path
			if(path > p1) {
				p2  = max(p2, p1); // replacing second max 
				p1 = path; 
			}
			else if ( path > p2)
			p2 = path;
		}
		//max distance
		d = max(d, p1 + p2);
		
		//adding the edge
		return max(p1,p2) + 1;
		
	}
	int diameter(Node* root) {
		int d = 0;
		dfsoOrPost(root, d);        
		return d;
	}
};

0
Reply
Share
Report
seeker256's avatar
Read More

My solution for distance with depth in C++

class Solution {
public:
    int diameter(Node* root) {
        diam = 0;
        maxDepth(root, 0);
        return diam;
    }

private:
    int diam;
    
    int maxDepth(Node* node, int curD) {
        if (node->children.size() == 0)
            return curD;
        
        int maxD1 = curD, maxD2 = 0;
        for (Node* child: node->children) {
            int depth = maxDepth(child, curD + 1);
            if (depth > maxD1) {
                maxD2 = maxD1;
                maxD1 = depth;
            } else if (depth > maxD2) {
                maxD2 = depth;
            }
            
            int dist = maxD1 + maxD2 - 2 * curD;
            diam = max(diam, dist);
        }
        return maxD1;
    }
};

0
Reply
Share
Report
onesuccess's avatar
Read More

My soln in C++

    int f(Node* root) {
        if (root == NULL) return 0;
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto &c: root -> children) {
            pq.push(f(c));
            if (pq.size() > 2) pq.pop();
        }
        auto l1 = 0, l2 = 0;
        if (pq.size() > 0) { l1 = pq.top(); pq.pop(); }
        if (pq.size() > 0) { l2 = pq.top(); pq.pop(); }
        
        res = max(res, l1 + l2);
        return 1 + max(l1, l2);
    }
    
    int diameter(Node* root) {
        f(root);
        return res;
    }

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium